Secret sharing schemes comprise a cryptographic tool for implementing secure distributed protocols, allowing the splitting of a secret (typically, a cryptographic key) into a number of randomly produced pieces, or shares, and their dispersal to corresponding entities, during a secret sharing phase. This secret may become available again, during a secret reconstruction phase, only by combining a number of these shares that satisfy some well defined conditions. Shamir's Secret Sharing Scheme (see, e.g., A. Shamir, “How to Share a Secret.” Communications of the Ass'n of Computer Machinery, Vol. 22, No. 11, 612-13 (1979)) is the most widely used secret sharing scheme, allowing secret reconstruction under threshold conditions.
In certain settings it is useful that one or more of the shares are chosen according to some external criteria (e.g., independently of the secret being split or the secret sharing method itself). Thus, techniques have been proposed or suggested for extending secret sharing schemes to support sharing of secrets into shares so that one or more shares take on some predetermined fixed values and not arbitrary values that are randomly chosen during the secret sharing phase. For example, U.S. patent application Ser. No. 14/577,206 (now U.S. Pat. No. 9,455,968), filed Dec. 19, 2014, entitled “Protection of a Secret on a Mobile Device Using a Secret-Splitting Technique with a Fixed User Share,” incorporated by reference herein, discloses the use of “fixed shares” for enabling flexible reconstruction policies of keys split using Shamir's sharing scheme that allow for the use of one or more user-defined shares (e.g., a password) during key reconstruction. U.S. patent application Ser. No. 14/672,507 (now U.S. Pat. No. 9,813,243), filed Mar. 30, 2015, entitled “Methods and Apparatus for Password-Based Secret Sharing Scheme,” incorporated by reference herein, describes threshold password-based secret sharing (or PBSS) schemes, where, during the secret sharing phase, one or more of the shares, into which a given secret is split, can take on some predetermined fixed values that can be provided as additional inputs to the secret sharing algorithm, without otherwise affecting the security of the scheme or its functionality during the secret reconstruction phase. Shares whose values depend on, or are fully specified by, criteria that are external to the shared secret (thus, taking on values that are predetermined and fixed prior to secret sharing), and therefore are typically independent of the shared secret, are generally referred to as fixed shares.
Nonetheless, a need remains for efficient proactivization techniques for threshold PBSS schemes that also allow updates of the split keys. A further need exists for general flexible key-rotation mechanisms for refreshment of secrets in the framework of password-based key splitting.